The recent rapid development in the information processing technology using computers has increased the importance of storing and managing critical electronic information such as corporate confidential information and personal information in a secure manner. In particular in the environment of crowd computing where users receive various services from a server via a network, there is a risk that the critical information on the network could be compromised, and various technologies have therefore been developed with the aim of removing such security risks.
The secret sharing method (threshold scheme) is known as such a technology. Secret data containing critical information is split into n shared data parts such that the secret data can be reconstructed when k or more of the n data parts are available. In particular, the method using polynomial interpolation is well known (see Non-Patent Document 1). According to this threshold scheme, as opposed to the encryption technology such as RSA (Rivest, Shamir and Adelman) encryption relying on the computational load for security, even when less than k shared data parts are acquired by a third party, the security of the secret data can be ensured without regard to the computational power of the information processing device (decryption device) which may be at the disposal of the third party from the viewpoint of the information theory.
On the other hand, as the threshold scheme requires a significant computational load (processing time) for the polynomial computations, this scheme may not be suitable for applications where a real time response is required or a large amount of data is required to be processed. As a technology that overcomes this problem, it is known to use XOR (exclusive logical sum) instead of polynomial interpolation. See Patent Document 1.